package com.util;
import java.math.BigDecimal;
import java.util.*;

/**
 * Created by Lenovo on 2017/8/9.
 * 道格拉斯-普克 Douglas-Peuker抽稀算法
 道格拉斯-普克抽稀算法，是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。
 该算法实现抽稀的过程是：
 1）对曲线的首末点虚连一条直线，求曲线上所有点与直线的距离，并找出最大距离值dmax，用dmax与事先给定的阈值D相比：
 2）若dmax<D，则将这条曲线上的中间点全部舍去；则该直线段作为曲线的近似，该段曲线处理完毕。
 　 若dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法，即重复1），2）步，直到所有dmax均<D，即完成对曲线的抽稀。
 显然，本算法的抽稀精度也与阈值相关，阈值越大，简化程度越大，点减少的越多，反之，化简程度越低，点保留的越多，形状也越趋于原曲线。
 *
 */
//lng 经度 lat 维度 lat（x） 横 lng(y) 竖
public class DLUtil {
	
    //阈值//TODO 待计算
    private static double THRESHOLD_VALUE = 30;
    private static double EARTH_RADIUS = 6378137; // 地球半径
    private static double [][]gpsList1 = null;
    
    public static void main(String[] args) {
    	int len = 8;
    	int size = 10000;
    	gpsList1 = new double[size][2];
    	for(int i=0;i<size;i++){
    		BigDecimal   x   =   new   BigDecimal(119+Math.random()*1);  
    		BigDecimal   y   =   new   BigDecimal(30+Math.random()*1);  
    		gpsList1[i][0] =x.setScale(len,   BigDecimal.ROUND_HALF_UP).doubleValue();
    		gpsList1[i][1] =y.setScale(len,   BigDecimal.ROUND_HALF_UP).doubleValue();
    	}
    	
        System.out.println("开始的长度为：  "+gpsList1.length);
        for(int i = 0;i<gpsList1.length;i++){
            System.out.println("new BMap.Point("+gpsList1[i][1]+", "+gpsList1[i][0]+"),");
        }
        
        changeGpsArray(gpsList1);
        
        System.out.println("最后的长度为：  "+gpsList1.length);
        for(int i = 0;i<gpsList1.length;i++){
//            System.out.println("new BMap.Point("+gpsList1[i][1]+", "+gpsList1[i][0]+"),");
        }
    }
    
    
    /**
     * 对有序的二维坐标进行一次道格拉斯-普克抽稀算法
     * @param gpsList
     */
    public static void changeGpsArray(double gpsList[][]) {
        //lng 经度 lat 维度 lat（x轴） 横 lng(y轴) 竖
        //第一个点坐标
        double x1 = gpsList[0][0];
        double y1 = gpsList[0][1];
        //最后一个点的坐标
        double x2 = gpsList[gpsList.length - 1][0];
        double y2 = gpsList[gpsList.length - 1][1];
        //距离list
        double[] disList = new double[gpsList.length-2];

        for (int i = 1; i < gpsList.length - 1; i++) {
            //1.得到曲线上的点到首末点连成直线的垂足（经纬度）.
            //2.获取垂足与曲线上的点的距离（经纬度转距离）
        double d = getpedal(x1, y1, x2, y2, gpsList[i][0], gpsList[i][1]);
            disList[i-1] = d;
        }
        //获取最大值与最大值在数组中的位置
        double dmax = (double) getDmax(disList).get("value");
        int index = (Integer) getDmax(disList).get("index")+1;
        System.out.println("最大值：  "+dmax+"    "+index);

        if(dmax<THRESHOLD_VALUE){//dmax<D，则将这条曲线上的中间点全部舍去
            removeGps(x1,y1,x2,y2);
            System.out.println("< 的长度为：  "+gpsList1.length);
            System.out.println("< 的长度为：  "+gpsList1.length);
        }else {//dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分,对这两部分重复使用该方法
            double[][] list1 = getNewList(gpsList,0,index-1);//保留点左边
            double[][] list2 = getNewList(gpsList,index+1,gpsList.length-1);//保留点右边
            System.out.println("list1的长度为：  "+list1.length+"   "+list1[list1.length-1][0]);
            System.out.println("list2的长度为：  "+list2.length+"   "+list2[0][0]);
            System.out.println(">= 的长度为：  "+gpsList1.length);
            if(list1.length>2){
                changeGpsArray(list1);
            }
            if(list2.length>2){
                changeGpsArray(list2);
            }
        }
    }
    //获取划分曲线
    private static double[][] getNewList(double list[][],int startIndex,int endIndex){
        double[][] newList = new double[endIndex-startIndex+1][2];
        int j =0;
        for(int i =startIndex;i<endIndex+1;i++){
            newList[j] = list[i];
            j++;
        }
        return newList;
    }
    //曲线上所有点与直线的距离的最大距离值dmax
    private static Map<String,Object> getDmax(double dmaxList[]){
        double dmax = 0;
        int j=0;
        for (int i =0;i<dmaxList.length;i++){
            if(dmax<=dmaxList[i]){
                dmax = dmaxList[i];
                j = i;
            }
        }
        Map<String,Object> map = new HashMap<>();
        map.put("value",dmax);
        map.put("index",j);
        return map;
    }
    //dmax<D，则将这条曲线上的中间点全部舍去
    private static void removeGps (double x1,double y1,double x2,double y2){
        int a=0,b=0;
        for(int i =0;i< gpsList1.length;i++){
            if(gpsList1[i][0] == x1 &&gpsList1[i][1] == y1){
                a = i;
            }
            if(gpsList1[i][0] == x2 &&gpsList1[i][1] == y2){
                b = i;
            }
        }
        List<double[]> list = new ArrayList<double[]>();
        for(int i =0;i< gpsList1.length;i++){
           if(i<=a||i>=b){
        		   list.add(gpsList1[i]);
           	}
           
        }
        double[][] gps = new double[list.size()][2];
        for(int i=0;i<list.size();i++){
        	gps[i] = list.get(i);
        }
        gpsList1 = Arrays.copyOf(gps,gps.length);
//        gpsList1 = Arrays.copyOf(gps,gpsList1.length+1-b+a);
    }
    //获取点到直线的垂足
    private static double getpedal(double x1, double y1, double x2, double y2, double x3, double y3) {
        double x12 = x1 - x2;
        double y12 = y1 - y2;
        double k1 = y12 / x12;//斜率1
        double k2 = -x12 / y12;//斜率2
        //求垂足的经纬度坐标
        double cx = (y3 - y1 + k1 * x1 - k2 * x3) / (k1 - k2);
        double cy = k2 * (cx - x3) + y3;
        double dis = Distance(cy, cx, y3, x3);
        return dis;
    }

    
    //计算点到垂足之间的距离
    private static double Distance(double long1, double lat1, double long2, double lat2) {//单位：米
        double a, b;
        lat1 = red(lat1);
        lat2 = red(lat2);
        a = lat1 - lat2;
        b = red(long1) - red(long2);
        double d;
        double sa2, sb2;
        sa2 = Math.sin(a / 2.0);
        sb2 = Math.sin(b / 2.0);
        d = 2* EARTH_RADIUS* Math.asin(Math.sqrt(sa2 * sa2 + Math.cos(lat1)* Math.cos(lat2) * sb2 * sb2));
        return d;
    }

    private static double red(double d) {
        return d * Math.PI / 180.0;
    }
}
